package com.lwl.Algorithmic_data_structure.class06堆排序;

import com.lwl.Utils.NumberUtils;

/**
 * 左孩子 2*i + 1
 * 右孩子 2*i + 2
 * <p>
 * 父节点 (i-1) / 2
 * <p>
 * 大根堆 所有子树都满足 头节点是整棵树最大值
 */
public class Code02HeapSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{1, 5, 10, 9, 5, 6, 3, 8, 4, 3, 5, 4, 3, 10, 1};
        int[] arr = NumberUtils.createRandomArrayRepeat(15, 10);
//        PrintUtil.printArray(arr);
        priorityQueue(arr);
//        PrintUtil.printArray(arr);
    }

    public static void priorityQueue(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            addInHeap(arr[i], arr, i);
        }
//        PrintUtil.printArray(arr);
        for (int i = 0; i < arr.length; i++) {
            int heapSize = arr.length - i - 1;
            NumberUtils.swap(arr, 0, heapSize);
//            System.out.println("=======" + i + "=======");
//            PrintUtil.printArray(arr);
            heapify(arr, heapSize);
//            PrintUtil.printArray(arr);
        }
    }

    // 下沉操作
    private static void heapify(int[] arr, int heapSize) {
        if (heapSize == 0) {
            return;
        }
        int curIndex = 0;
        int left = curIndex * 2 + 1;
        while (left < heapSize) {
            int largestChildIndex = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
            if (arr[curIndex] < arr[largestChildIndex]) {
                NumberUtils.swap(arr, curIndex, largestChildIndex);
                curIndex = largestChildIndex;
                left = curIndex * 2 + 1;
            }
            if (curIndex != largestChildIndex) {
                break;
            }
        }
    }

    /**
     * 将num放入到arr[heapSize]的位置上
     * 在进行上浮操作
     */
    private static void addInHeap(int num, int[] arr, int heapSize) {
        int curIndex = heapSize;
        while (curIndex != 0) {
            int parentIndex = (curIndex - 1) / 2;
            // 和父节点进行比较
            if (arr[curIndex] > arr[parentIndex]) {
                NumberUtils.swap(arr, curIndex, parentIndex);
                curIndex = parentIndex;
            }
            // 此时没有进一步上浮了,跳出循环
            if (curIndex != parentIndex) {
                break;
            }
        }
    }
}
